In variable length coding (VLC), source symbols of a fixed length are encoded as codes having a variable length. Variable length coding is a widely used technique for lossless data compression. For instance, VLC is used in the Motion Pictures Expert Group (MPEG), Joint Photographics Expert Group (JPEG), CCITT H.261 and H.262 standards. Variable length coding (VLC) technique is used to encode frequently occurring fixed length source symbols with shorter codes and infrequently occurring fixed length source symbols with longer codes. In general, the length of the code for a fixed length source symbol is designed to be inversely proportional to the probability of the occurrence of the symbol. Thus, the VLC takes advantage of a non-uniform distribution in the occurrence of the fixed length source symbols. The most wellknown example of a variable length code is the Huffman code.
Variable length code words (VLCWs) may be produced by a serial encoder or a parallel encoder. A serial encoder outputs one bit at a time. A parallel encoder outputs a group of bits (e.g., a group 8 bits ) at a time, in parallel. Conventional VLC techniques are disclosed in M. Stroppiana, L. Ronchetti, Device for reducing the redundancy in blocks of digital video data in DCT encoding U.S. Pat. No. 5,006,930, 1991.4.9., F. Azadegan, E. Fisch, Method and apparatus for digitally processing a high definition television augmentation signal U.S. Pat. No. 5,128,758, 1992.7.7., S. M. Lei, M. T. Sun, An Entropy Coding System for Digital HDTV Application, IEEE Trans. on Circuit and system for Video tech., vol. CASV-1, no. 1, pp. 147-155, February 1991, F. Azadegan, Method and apparatus for digitally processing a high definition television augmentation signal, U.S. Pat. No. 5,179,442, 1993.1.1 2., G. J. Kustka, Variable length decoder, U.S. Pat. No. 5,226,082, 1993.7.6., K. C. Chu, etc., Variable length decoding using lookup tables, U.S. Pat. No. 5,253,053, 1993.10.12., H. Brusewitz, Method and means for variable length coding, U.S. Pat. No. 4,922,510, 1990.5.1., F. Mikami, Variable-length coding/decoding device, U.S. Pat. No. 4,985,700, 1991.1.1 5., N. Shirota Coding and decoding apparatus of variable length data U.S. Pat. No. 5,162,795, 1992.11.10., which are incorporated herein by reference.
According to the MPEG and JPEG standards, the variable length codes are used to encode a pair of values, referred to as a run-level pair. The run-level pair represents a variable length sequence of values including a last value having an amplitude equal to the level of the run-level pair. The sequence also includes a subsequence or "run" of zero or more values having an amplitude of zero. The number of zeros in the "run" is equal to the "run" value of the run-level pair. For example, in the MPEG standard, the sequence 380005001 is represented as (0,38)(3,5)(2,1), where the run-level pair (0,38) indicates that there are no zeros before the number 38, the run-level pair (3,5) indicates that there are 3 zeros before the number 5; and the run-level pair (2,1) indicates that there are 2 zeros before the number 1.
FIG. 1 provides a variable length code table for the CCITT recommendation H.261. The table encodes each of 127 fixed length code words as a corresponding unique VLCW. Each fixed length code word is a pair of a run and a level. The level may be a positive or a negative value. The variable length code associated with each fixed length code word has a sign bit "s" for indicating whether the level has a positive polarity (i.e., s=0) or a negative polarity (i.e., s=1).
FIG. 2 is a variable length decoding table for decoding each variable length code word into a run-level pair. As shown, the variable length decoding table also produces a length value in decoding each VLCW. The purpose of the length value is discussed below.
FIG. 3 shows a conventional parallel variable length parallel encoder 100. The conventional variable length parallel encoder 100 is used for encoding fixed length code words, such as run-level pairs, into variable length code words that are, for example, from 2 bits to 17 bits long. The encoder 100 illustratively includes a PLA (Programmable Logic Array) 110 that stores a code word table 120 and a code length table 130. The PLA 110 receives the fixed length run-level pairs of n bits on line 140.
In response to each run-level pair, the code word table 120 outputs the corresponding variable length code word (VLCW). The code length table 130 outputs a length which equals the number of bits in the VLCW produced by the code word table 120. The VLCW and the length are provided to a circuit 150 on line 160 and 170, respectively. The circuit 150 contains a barrel shifter, registers and a code-length accumulation circuit. The circuit 150 concatenates the VLCWs and arranges the concatenated VLCWs in groups (e.g., byte sized groups) for transmission on line 180.
It should be noted that the VLCWs are chosen so that no shorter code comprises a subset of the bits in a longer code. For this reason, a decoder cannot "mistakenly" recognize and decode a shorter code when it is supposed to receive a longer code. Thus, it is not necessary to explicitly transmit the code length information with each VLCW. Rather, the length value is used by the circuitry 150 of the encoder 100 to concatenate the VLCW together to form one continuous sequence of bits. The bits of the sequence may be stored in a register for later transmission on line 180 to a variable length decoder (VLD).
FIG. 4 shows a variable length decoder (VLD) 200 which was proposed in J. W. Peake, "Decompaction," IBM Technical Disclosure Bulletin vol. 26, no. 9, p. 4794-97, February, 1984. An inputted bitstream to be decoded is formed from the concatenation of VLCWS outputted from the VLC 100 (FIG. 3). P number of bits of the bitstream are received in parallel, on lines 210, in two latches L1 and L2, so that a total of 2P consecutive bits may be stored in the latches L1 and L2. Here, P=the length of the longest variable length code word (VLCW), e.g., 17 bits.
A barrel shifter 230 outputs a P bit "window" i.e., a P bit subsequence, of the 2P consecutive bits stored in the latches L1 and L2. The bits of the next VLCW to be decoded are aligned with the most significant bit of the P bit window. For instance, assume the bits in the received bit stream are f.sub.y...f.sub.2 sg.sub.w...g.sub.2 s..., where:
A typical P bit window includes, in most significant bit order to least significant bit order, the bit order f.sub.y...f.sub.2 sg.sub.w...g.sub.y-z, where P=y+z-1. The window of P bits is received in parallel at a pair of PLAs 240, 250. The PLA 240 decodes only the bits of the very next VLCW, i.e., f.sub.y...f.sub.2 s, and outputs the decoded run-level pair corresponding thereto. Note that only one VLCW can be decoded from the P bit window (assuming the most-significant bit of the P-bit window is justified with the very next undecoded bit) since no VLCW can be formed by concatenating two other (shorter) VLCWs.
Note that there is no prior knowledge of the length of each VLCW in the bitstream received on line 210. It is necessary to determine which subsequence of the P-bit window formed the most recently decoded VLCW, so that those bits can be removed to align the very next undecoded VLCW with the most significant bit of the P-bit window. To that end, an additional PLA 255 is provided for decoding each VLCW into the respective length (number of bits) of the VLCW. The decoded length is fed back to the barrel shifter 230 which shifts out the bits of the last decoded VLCW. Effectively, the barrel shifter 230 discards the bits of the most recently decoded VLCW and obtains a P-bit window of the P very next consecutive undecoded bits with the most significant bit of the window aligned with the very next undecoded bit.
The decoded run-level pair is outputted to a run length decoder (RLD) 290 which reproduces the original sequence, namely, the level followed by a sequence of zeros (the number of which is specified by the run value).
Inspection of the VLD decoding tables used in JPEG, MPEG I and MPEG II, reveals that the PLA decoding table contains 114 variable length code words the longest of which has a length of 17 bits. The least significant bit (represented by s) of each of the 114 variable length codes indicates whether the variable length code is a positive or a negative number. If s is 0, the decoded level of the variable length code is a positive number. If s is 1, the decoded level is a negative number.
Typically, a VLD does not know in advance if a particular code, to be decoded next, is positive or negative. To cope with this problem, the conventional VLD design uses two variable length decoding tables 240, 250; one variable length decoding table 240 for positive levels where "s", the sign bits are zero (i.e., s=0), and another variable length decoding table 250 for negative levels where s=1. Both PLA tables 240, 250 receive the variable length code words from the barrel shifter 230.
As shown in FIG. 4, if the sign bit s is 0, then the positive variable length decoding table 240 is used. If the sign bit s is 1, then the negative variable length decoding table 250 is used. A multiplexer 260 may be provided for selecting the output of the appropriate table 240 or 250. Depending on the sign bit s, the output 270 of the variable length decoding table 240 (for s=0), or the output 275 of the variable length decoding table 250 (for s=1) is selected by the multiplexer 260. The multiplexer 260 outputs one of the variable length decoding table outputs 270, 275 on line 280 to the RLD 290.
Alternatively, instead of using two variable length decoding tables 240, 250 and the multiplexer 260, only one decoding table may be used that has a storage area which equals the storage area of the two variable length decoding tables 240, 250 combined.
The parallel VLD 200 requires two variable length decoding tables 240, 250, (or one large variable length decoding table having a size which equals the size of the two tables 240, 250 combined) for decoding both positive and negative VLCWs. This necessitates a large memory area requirement which consumes valuable real estate, prevents compactness, increases cost and reduces the decoding speed.
Accordingly, it is an object of the present invention to reduce the size of the VLD decoding table. Another object of the present invention is to reduce the area or storage requirements of the PLA or ROM (Read Only Memory) and increase the decoding speed.